1. Field of the Invention
The present invention relates to a processor allocating method and a processor allocating system used in a multiprocessor system for allocating processors to tasks executed in a parallel mode in this multiprocessor system, and also relates to a storage medium capable of storing a processor allocation program.
2. Description of the Related Art
In a multiprocessor system, a process operation of a single program is subdivided into a plurality of tasks, and then the plural tasks are executed by a plurality of processors in a parallel manner, so that turn around time of this program may be reduced. These tasks are called "parallel tasks". To shorten the turn around time of the program constituted by the parallel tasks, it is important to allocate the processors to the respective tasks in a high efficiency.
On the other hand, when a process operation of a single program is subdivided into a plurality of tasks to be executed, communications must be carried out among the respective tasks. It is also important for improving process performances to reduce overheads required for these task communications.
Generally speaking, communication times established among these processors for constituting a multiprocessor are different from each other, depending upon connection types among processors and physical distances among processors.
For instance, in such a multiprocessor system arranged by coupling a plurality of nodes with each other via a network, which are constructed of plural processors coupled by shared memories, communication speeds among the processors connected via the network are very slower than those among the processors connected via the shared memories.
In a hipercube-connected multiprocessor system, when each of tasks for constituting parallel tasks is executed on a multiprocessor, one scheduling method is described in Japanese Kokai Patent Application No. 2-226358. That is, the respective tasks are allocated to the processors of the multiprocessor system in order to reduce the overhead of the communication process operations executed among the processors.
In this scheduling method, the tasks are allocated to the processors in such a manner that the coincident degrees between the structures of the task graphs for representing the relationship among the tasks and the structures of the hypercubes become maximum.
However, the multiprocessor system to which this conventional scheduling method can be applied is limited only to the hypercube-connected type multiprocessor system. Therefore, there is a problem that this scheduling method cannot be applied to any other types of multiprocessor systems.
As known in the art, the communication times would be greatly varied in accordance with the communication amounts executed among the processors. Since the processors are allocated to the tasks without considering the communication amounts among the tasks, there is another problem. That is, very lengthy communication time among the tasks is required when two processors whose communication times become very long are allocated to such two tasks that data communication amounts between these two tasks are very large.